bonsoon's blog |
| latest | about | random
# 2 - More consequences of the reals. We saw that the reals is the essentially unique Dedekind complete ordered field, is maximally Archimedean and contains the rationals as a dense subset. We can view Dedekind completeness as a way of "patching up holes" in the rationals. In this view point, we can look at other forms of "completeness", and some in fact are equivalent to being Dedekind completeness! - Monotone completeness - Nested completeness - Bolzano and Weierstrass completeness - Cauchy completeness - Cut completeness Can you guess which ones above are equivalent to Dedekind completeness? ## Some preliminaries: Absolute value, triangle inequality, sequences. In an ordered field $R$, we can define the **absolute value** of an element $|x| = \begin{cases}x &\text{if }x\ge 0 \\ -x &\text{if} x < 0\end{cases}$. Note we always have $-|x| \le x \le |x|$ and $|-x| = |x|$. With this, we have >Triangle inequality in an ordered field. For any $x,y$ in an ordered field $R$, we have $|x + y| \le | x| + |y |$. $\blacktriangleright$ We can just look at all cases. Suppose $x+y \ge 0$, then $|x+y| = x + y \le |x| + |y|$. Suppose $x + y < 0$, then $-x-y > 0$, so $|x+y| = |-x-y| = -x-y \le |x| + |y|$. $\blacksquare$ --- Next we define what it means for a sequence to converge in an ordered field $R$. Let $(a_{n})$ be a sequence in $R$. We say $a_{n}$ **converges** to a **limit** in $R$ if there exists some element $a \in R$ such that for any positive $\epsilon > 0$ in $R$, there exists some positive integer $N$ where $n \ge N$ implies $a_n \in (a-\epsilon , a + \epsilon)$, equivalently $|a - a_{n}| < \epsilon$. In this case we write $a_{n} \to a$, or write $\lim a_{n} = a$. In other words, if $a_{n} \to a$, then every open interval about $a$ contains an eventual infinite tail of the sequence $a_{n}$. Remark. This is consistent with convergence if $R$ is to inherit the order topology. First some results about convergence in an ordered field. > If a sequence $(a_{n})$ in an ordered field converges, then the limit is unique. $\blacktriangleright$ Indeed, suppose $a_{n} \to a$ and $a_{n} \to b$. If to the contrary that $a\neq b$, take $\epsilon = \frac{1}{2}|a - b|$. Then there exists some $N$ where $n\ge N$ implies $a_{n} \in (a- \epsilon, a+ \epsilon)$. But for each of these $a_{n}$, we have $|a_{n}-b| > \epsilon$, contradicting that $a_{n} \to b$. $\blacksquare$ Observe that $a_{n}\to a$ if and only if $a-a_{n}\to 0$ if and only if $|a-a_{n}|\to 0$ in an ordered field $R$. A curiosity to ponder, does the sequence $a_{n} = \frac{1}{n}$ converge in an ordered field $R$ ($n$ positive integers)? Well, if $R$ is Archimedean then yes. If not Archimedean, then not necessarily! --- We say a set $S$ is **bounded** in ordered field $R$ if there exists $M \in R$ such that $|x| \le M$ for all $x \in S$. And we say a sequence $(a_{n})$ is **bounded** if there exists $M \in R$ such that $|a_{n}| \le M$ for all $n$. We say a sequence $(a_{n})$ is **monotone** if either, - for all $n$ we have $a_{n} \le a_{n+1}$, which we call monotone increasing, or - for all $n$ we have $a_{n} \ge a_{n+1}$, which we call monotone decreasing. If the inequality is strict they we use the adjective **strictly monotone**. ## Monotone completeness. Let $R$ be an ordered field. We say $R$ is **monotone complete** if every bounded monotone sequences in $R$ converges in $R$. > The reals $\mathbf{R}$ is monotone complete. $\blacktriangleright$ Take a bounded monotone sequence $(a_{n})$ in $\mathbf{R}$, say $a_{n}$ is monotonically increasing, that $a_{n} \le a_{n+1}$ for all $n$, and that $M$ is an upper bound. Then for all $n$, we have $a_{n} \le M$, so the set $A = \{a_{n}\}$ has least upper bound $a = \sup A$ in $\mathbf{R}$ by Dedekind completeness. We claim $a_{n} \to a$. Indeed, take any $\epsilon > 0$. Then $a - \epsilon$ is not an upper bound of $A$, so there exists some $a_{N}$ such that $a_{N} > a - \epsilon$, or $a - a_{N} < \epsilon$. Since $(a_{n})$ is monotonically increasing, we have $n \ge N$ implies $a_{n} \ge a_{N}$, so $a-a_{n} < \epsilon$ whenever $n \ge N$. Finally, as $a \ge a_{n}$, we have $|a_{n} - a| = |a-a_{n}| = a-a_{n} < \epsilon$, whenever $n \ge N$. This shows $a_{n} \to a$. One can similarly show for bounded monotonically decreasing sequences. $\blacksquare$ Remark. This is nice as it asserts the existence of a limit without knowing what the limit is a priori. **Remark.** This also shows, for $R$ an ordered field, $$ R \text{ is Dedekind complete} \implies R \text{ is monotone complete.} $$ ## Nested completeness. Let $R$ be an ordered field, we say $R$ is **nested complete**, or has the **nested interval property**, if every sequence of bounded nested closed intervals $I_{n}=[a_{n},b_{n}]$, where $I_{1}\supset I_{2}\supset I_{3} \supset \cdots$, their common intersection is not empty, namely $\bigcap I_{n} \neq \varnothing$ . > The reals is nested complete. $\blacktriangleright$ Note the left end points forms a sequence $(a_{n})$​ that increases monotonically, and each right end point $b_n$​ is an upper bound of the sequence $(a_{n})$. Hence by bounded monotone sequence theorem, $a_{n}\to a = \sup a_{n}$ . Since $a$ is an upper bound of $a_{n}$, we have $a_{n}\le a$ for each $n$ . And since each $b_{n}$ is an upper bound of $a_{n}$ , we have $a\le b_{n}$ as $a$ is the least upper bound. Thus $a_{n}\le a\le b_{n}$ for each $n$, namely $a \in I_{n}$ for each $n$. $\blacksquare$ Furthermore, if the intervals also shrinks, then we have a singleton intersection: > Let $I_{n} = [a_{n},b_{n}]$ be bounded nested intervals in the reals $I_{1}\supset I_{2}\supset I_{3}\supset\cdots$ where the lengths of the interval $|I_{n}| =b_{n}-a_{n}\to0$. Then $\bigcap I_{n} = \{\ast\}$ is a singleton set. $\blacktriangleright$ Since we established that $a = \sup a_{n} \in \bigcap I_{n}$, we now show that is the only point in the intersection if the intervals shrink. If there exists another point $a' \in \bigcap I_{n}$, then note there is an interval $I_{N}=[a_{N},b_{N}]$ where $|I_{N}| < |a-a'|$, since $|I_{n}|\to 0$. But $a_{N}\le a,a' \le b_{N}$, so $|a-a'| \le b_{N}-a_{N}=|I_{N}|$, a contradiction. $\blacksquare$ **Remark.** This is false if replaced with open nested intervals, or unbounded intervals. **Remark.** We can extend this to higher dimensions, by noting that each side of the boxes form nested intervals. ## Bolzano and Weierstrass completeness Given a sequence $(a_{n})$ in a set $R$, a **subsequence** of $(a_{n})$ is a sequence $(a_{n(k)})_{k=1}^{\infty}$ where $n(k):\mathbb{N}\to\mathbb{N}$ is a strictly increasing indexing function, with $n(k) < n(k')$ whenever $k < k'$. We say an ordered field $R$ is **Weierstrass complete** if every bounded sequence $(a_{n})$ has a convergent subsequence $(a_{n(k)})$. > The reals $\mathbf{R}$ is Weierstrass complete. $\blacktriangleright$ One way to show this is to construct a subsequence by repeated bisection, or "how to catch a lion". Since $(a_{n})$ is bounded, say the terms are all contained in the closed interval $I_{0}=[-M,M]$. Bisect this interval into two closed intervals, $I_{1}^{(L)}$ and $I_{1}^{(R)}$. By pigeonhole principle, one of these two haves will contain infinitely many terms of the sequence $(a_{n})$. Denote the half with infinitely many terms as $I_{1}=I_{1}^{(X)}$, $X\in\{L,R\}$. In $I_{1}$, pick any term from our sequence to be the first term for our subsequence, say $a_{n(1)}$. Now bisect $I_{1}$ into two closed intervals $I_{2}^{(L)}$ and $I_{2}^{(R)}$. Again by pigeonhole, there will be one that has infinitely many terms of the sequence. Denote it to be $I_{2}$ and pick a term $a_{n(2)}$ with $n(2)>n(1)$. Repeat this, at each stage with the interval $I_{k}$, bisect it into two halves $I_{k+1}^{(L)}$ and $I_{k+1}^{(R)}$ and denote $I_{k+1}$ to be the one with infinitely many terms. Pick $a_{n(k+1)}\in I_{k+1}$ such that $n(k+1)>n(k)$. This is possible because there are infinitely many terms in $I_{k+1}$! Now by nested interval theorem, the closed intervals $I_{k}$ are nested with $|I_{k}|=\frac{|I_{0}|}{2^{k}}\to0$. So $\bigcap I_{k}=\{a^{*}\}$. We claim the subsequence $a_{n(k)}\to a^{*}$. Note $a_{n(k)}\in I_{k}$ and that $a^{*}\in I_{k}$. So $|a_{n(k)}-a^{*}|\le|I_{k}|=\frac{|I|}{2^{k}}\to0$. Hence $a_{n(k)}\to a^{*}$. $\blacksquare$ --- There is a set-theoretic version of this sequential form. Given a subset $A$ of an ordered field $R$, we say a point $p\in R$ is an **adherent point** of $A$ if every open interval $I$ about $p$ intersects $A$. Note $p$ need not be in $A$. And we say a point $p \in R$ is a **limit point** of $A$ if every open interval $I$ about $p$, the punctured interval $I\setminus\{p\}$ intersects $A$. Note, every limit point is an adherent point, but not the other way around. An adherent point that is not a limit point is called an **isolated point**. Note $p$ is an isolated point of $A$ is equivalent to saying $p\in A$ and there exists an open interval $I$ about $p$ such that $I\cap A=\{p\}$. Note if a sequence $(a_{n})$ has all distinct terms, and $a_{n}\to a$, then $a$ is a limit point of the set $\{a_n\}$. In general, whenever a sequence converges $a_{n}\to a$, then $a$ is an adherent point of the set $\{a_{n}\}$. We say an ordered field $R$ is **Bolzano complete** if every infinite bounded subset $A \subset R$ has an limit point $p \in R$ for $A$. > The reals $\mathbf{R}$ is Bolzano complete. $\blacktriangleright$ Take an infinite bounded subset $A$ of reals. Then we can construct a sequence $(a_{n})$ with all distinct elements in $A$. Since the reals are Weierstrass complete, this sequence has a convergent subsequence with some limit $a \in \mathbf{R}$. This point $a$ is a limit point of a subset of points of $A$, and hence is also a limit point of $A$. $\blacksquare$ Note, $\mathbf{R}$ is Bolzano complete can also be directly proved without Weierstrass, Cauchy, or nested intervals, and directly from Dedekind completeness. We will use a generic lemma about finite sets in an ordered set. > **Lemma.** Let $R$ be an ordered set, and suppose $A \subset R$ is such that every nonempty $S\subset A$ is such that $\inf S\in S$ and $\sup S \in S$. Then $A$ is a finite set. $\blacktriangleright$ Suppose to the contrary that $A$ is an infinite set. Take any $x_{1} \in A$. And recursively define $$ x_{n} = \inf (A \setminus\{x_{1},\ldots,x_{n-1}\}). $$Note by property of this set $A$, each $x_{k} \in A$. Note the sequence $(x_{n})$ is strictly increasing. So now take $S = \{x_{1},x_{2},\ldots\}\subset A$, which we have $\sup S \in S$, where $\sup S = x_{N}$ for some $N$. But this is a contradiction, since $(x_{n})$ is strictly increasing, no element is an upper bound of $S$! $\blacksquare$ Now we prove Bolzano completeness for $\mathbf{R}$. $\blacktriangleright$ Take an infinite bounded subset $A$ of real numbers. Suppose to the contrary that it has no limit point in $\mathbf{R}$. Take any nonempty subset $S \subset A$. Since $S$ is also bounded, and that $\mathbf{R}$ is Dedekind complete, $\sup S$ and $\inf S$ exists in $\mathbf{R}$. If $\sup S \not\in S$, then this means $\sup S$ is a limit point of $S$, whence a limit point of $A$, contradiction. So $\sup S\in S$, and similarly $\inf S \in S$. But by lemma this means $A$ is finite! Contradiction! $\blacksquare$ **Remark.** Quite often both of these are collectively known as Bolzano-Weierstrass theorem. --- An alternate way of proving Weierstrass completeness for the reals is use monotone completeness and that every bounded sequence has a monotone subsequence in an ordered field: > Let $R$ be an ordered field, and let $(a_{n})$ be a bounded sequence in $R$. Then $(a_{n})$ admits a monotone subsequence $(a_{n(k)})$. $\blacktriangleright$ For the term $a_{n}$ of the sequence, call it a **peak** if it is greater than or equal to all terms that follows, $a_{n} \ge a_{m}$ for all $m\ge n$. If the sequence $(a_{n})$ has infinitely many peaks, giving a subsequence $(a_{n(k)})$, then this subsequence is monotonically decreasing. Done If the sequence $(a_{n})$ has only finitely many peaks, then consider the index position $n(1)$ where it is the first position that $a_{n(1)}$ is not a peak. And since $a_{n(1)}$ is not a peak, there exists some index $n(2) > n(1)$ such that $a_{n(2)} > a_{n(1)}$. Since $a_{n(2)}$ is not a peak as well, we can find a next index $n(3) > n(2)$ such that $a_{n(3)} > a_{n(2)}$, and that $a_{n(3)}$ is not peak. Continuing this gives a subsequence $(a_{n(k)})$ that is monotonically increasing. $\blacksquare$ ## Cauchy completeness Let $(a_{n})$ be a sequence in an ordered field $R$. We say $(a_{n})$ is a **Cauchy sequence** if for every positive $\epsilon > 0$ in $R$, there exists $N$ such that whenever $m,n \ge N$, we have $|a_{m}-a_{n}| < \epsilon$. And if in an ordered field $R$ every Cauchy sequence converges, then we say $R$ is **Cauchy complete**. A few lemmas about Cauchy sequences in ordered fields in general. > **Lemma.** If $(a_{n})$ is a Cauchy sequence in an ordered field $R$, then $(a_{n})$ is bounded. $\blacktriangleright$ Fix $\epsilon = 1$, then there exists index $N$ such that $n\ge N$ implies $|a_{n} - a_{N}| < 1$. Denote $M = \max(|a_{1}|,\ldots,|a_{N}|)+1$. Then for $k = 1,\ldots N$, we have $|a_{k}| \le M$, and when $k\ge N$, we have $|a_{k}|\le |a_{k}-a_{N}| + |a_{N}| < 1+|a_{N}| \le M$. $\blacksquare$ > **Lemma.** If $(a_{n})$ is a Cauchy sequence in an ordered field $R$, and $(a_{n})$ admits a convergent subsequence $(a_{n(k)})$ where $\lim_{k} a_{n(k)} =a$. Then $a_{n}\to a$, that is the Cauchy sequence also converges. $\blacktriangleright$ Fix any $\epsilon > 0$. Since $(a_{n})$ is Cauchy, there exists some $N$ such that $m, n \ge N$ implies $|a_{m}-a_{n}| < \frac{\epsilon}{2}$. Now, the subsequence $a_{n(k)}\to a$, so there exists some $K$ such that $n(K) > N$, and $k \ge K$ implies $|a_{n(k)}-a| < \frac{\epsilon}{2}$. So when $n \ge N$, we have $|a_{n}-a| \le |a_{n}- a_{n(K)}|+|a_{n(K)}-a| < \epsilon$. $\blacksquare$ Together, this gives > The reals $\mathbf{R}$ is Cauchy complete. $\blacktriangleright$ Take a Cauchy sequence $(a_{n})$ in the reals. Then by lemma, it is bounded. And as the reals is Weierstrass complete, there exists a convergent subsequence. But by other lemma, a Cauchy sequence admitting a convergent subsequence is itself convergent. Hence $\mathbf{R}$ is Cauchy complete. ## Cut complete. An ordered field $R$ is **cut complete** if for every **cut-partition** $R = A\cup B$ with $A < B$ and $A,B\neq\varnothing$, there exists $r \in R$ such that $\{x\in R:x < r\} \subset A$ and $\{x\in R: x > r\} \subset B$. Here, by $A < B$ it means $a\in A$ and $b\in B$ implies $a < b$. > $R$ is Dedekind complete (hence reals) if and only if $R$ is cut complete. $\blacktriangleright$ ($\implies$) Suppose $R$ is Dedekind complete, and take a cut-partition $A\cup B = R$ with $A < B$ and $A,B\neq\varnothing$. Since $A$ is not empty and bounded above, $a=\sup A$ exists in $R$. If $x < a$, then $x$ cannot be in $B$, otherwise this means $x$ is an upper bound of $A$, whence $a \le x$, a contradiction. So $\{x\in R: x< a\}\subset A$. If $x > a$, then $a$ is a strict upper bound of $A$, and cannot be in $A$, so $x \in B$. This shows $R$ is cut complete. ($\impliedby$) Suppose $R$ is cut complete, take $\varnothing \neq X\subset R$ that is bounded above by some $u \in R$. Take $B = \{r\in R:r\ge x \text{ for each } x\in X\}$, namely, all upper bounds of $X$, and take $A = R-B$. Note $u \in B$, so $B\neq\varnothing$. Note as $X$ not empty, it has some $x\in X$, and since the element $x-1 < x$, we have $x-1 \not\in B$, whence $x-1 \in A$. So $A\neq\varnothing$. Now take any $a\in A$ and $b\in B$. If $a \ge b$, then $a$ is an upper bound of the set $X$, making $a \in B$, a contradiction. So $A < B$ and this forms a cut-partition of $R$. Now, as $R$ is cut complete, there exists some element $r \in R$ such that $\{x < r\} \subset A$ and $\{x > r\}\subset B$. We now claim $\sup X$ exists. If $X$ has a maximum, then $\sup X = \max X$. So suppose $X$ has no largest element, which means every upper bound of $X$ is not in $X$, or $X \subset A$. In this case, we claim $r = \sup X$. If $r$ is not an upper bound of $X$, then there exists some $x \in X \subset A$ such that $x > r$. But $x > r$ implies $x\in B$, a contradiction. So $r$ is an upper bound of $X$. Now take any upper bound $u$ of $X$, then we have $u \in B$. If $u < r$, then $u \in A$, a contradiction. So $r \le u$, whence $r$ is the least upper bound of $X$. $\blacksquare$ ## A summary. In any ordered field $R$, denote $R_{\mathbf{Q}}$ to be the copy of the rationals in $R$, then $$ R \text{ is Archimedean} \iff R_{\mathbf{Q}}\text{ is dense in }R. $$ The reals $\mathbf{R}$ is axiomatically defined to be the essentially unique Dedekind complete ordered field, and that $$ \begin{array}{} & R \text{ is Dedekind complete} \\ \swarrow & \downarrow\uparrow & \searrow\nwarrow \\ R \text{ is Archimedean} & R \text{ is cut complete} & R \text{ is monotone complete} \\ \downarrow\uparrow & & \downarrow \\ R_{\mathbf{Q}} \text{ is dense in }R & & R \text{ is nested complete} \\ & & \downarrow \\ & R \text{ is Bolzano complete } \leftarrow & R \text{ is Weierstrass complete} \\ & & \downarrow \\ & & R \text{ is Cauchy complete} \end{array} $$ B / 7 2024